
#include "Game.h"
#include <float.h>

/* gets extent of vertices */
static void vertices_get_extent (const vertex_t* vl, int np, /* in vertices */
						  rect_t*  rc /* out extent*/ )
{
	int i;        
	if (np > 0){
		rc->min_x = rc->max_x = vl[0].x; rc->min_y = rc->max_y = vl[0].y;
		}else{
			rc->min_x = rc->min_y = rc->max_x = rc->max_y = 0; /* =0 ? no vertices at all */
			}

	for(i=1; i<np; i++)
		{
		if(vl[i].x < rc->min_x) rc->min_x = vl[i].x;
		if(vl[i].y < rc->min_y) rc->min_y = vl[i].y;       
		if(vl[i].x > rc->max_x) rc->max_x = vl[i].x;
		if(vl[i].y > rc->max_y) rc->max_y = vl[i].y;
		}
}

/* p, q is on the same of line l */
static int is_same(const vertex_t* l_start, const vertex_t* l_end, /* line l */
				   const vertex_t* p, 
				   const vertex_t* q)
{
	pointVertex dx = l_end->x - l_start->x;
	pointVertex dy = l_end->y - l_start->y;

	pointVertex dx1= p->x - l_start->x;
	pointVertex dy1= p->y - l_start->y;

	pointVertex dx2= q->x - l_end->x;
	pointVertex dy2= q->y - l_end->y;

	return ((dx*dy1-dy*dx1)*(dx*dy2-dy*dx2) > 0? 1 : 0);
}

static int is_sameline(const vertex_t* vertex, const vertex_t* p1, const vertex_t* p2)
{
	vertex_t vertexTmp1;
	vertex_t vertexTmp2;

	VERTEXSUB(vertex, p1, &vertexTmp1)
	VERTEXSUB(p2, p1, &vertexTmp2)

	if ((VERTEXCHENG(&vertexTmp1, &vertexTmp2) > -50) && (VERTEXCHENG(&vertexTmp1, &vertexTmp2) < 50))
	{
		return TRUE;
	}
	return FALSE;
}

static int is_in2prect(const vertex_t* vertex, const vertex_t* p1, const vertex_t* p2)
{
	if ((MIN(p1->x, p2->x) <= vertex->x) && ((MAX(p1->x, p2->x) >= vertex->x))
		&& (MIN(p1->y, p2->y) <= vertex->y) && ((MAX(p1->y, p2->y) >= vertex->y)))
	{
		return TRUE;
	}
	return FALSE;
}

/* 2 line segments (s1, s2) are intersect? */
static int is_intersect(const vertex_t* s1_start, const vertex_t* s1_end, 
						const vertex_t* s2_start, const vertex_t* s2_end)
{
	return (is_same(s1_start, s1_end, s2_start, s2_end)==0 && 
		is_same(s2_start, s2_end, s1_start, s1_end)==0)? 1: 0;
}

static void TS2Pol(vertex_t* vtgt, int* nptgt, const vertex_t* vsrc, int npsrc)
{
	short i = 0;

    (*nptgt) = 0;
	for (i=0; (i<npsrc)&&(i<1024) ;i++)
	{
		if (i%2 != 0)
		{
			(vtgt+(*nptgt))->x = (vsrc+i)->x;
			(vtgt+(*nptgt))->y = (vsrc+i)->y;
			(vtgt+(*nptgt))->z = (vsrc+i)->z;
			(*nptgt) += 1;
		}
	}
	for (i=npsrc-1; i>-1 ;i--)
	{
		if (i%2 == 0)
		{
			(vtgt+(*nptgt))->x = (vsrc+i)->x;
			(vtgt+(*nptgt))->y = (vsrc+i)->y;
			(vtgt+(*nptgt))->z = (vsrc+i)->z;
			(*nptgt) += 1;
		}
	}
	(vtgt+(*nptgt))->x = (vsrc)->x;
	(vtgt+(*nptgt))->y = (vsrc)->y;
	(vtgt+(*nptgt))->z = (vsrc)->z;
	(*nptgt) += 1;

	return;
}

int pt_in_linestrip (   const vertex_t* vl, int np,  /* polygon vl with np vertices  */
				const vertex_t* v)
{
	int i = 0;
	int j = 0;
	short i2ret = FALSE;
	rect_t		rc; 

	if (np < 2)
		return 0; 

	vertices_get_extent(vl, np, &rc);
	if ((v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) != 0)
	{
		return i2ret;
	}
	
	for (i=0; i<np-1; i++)
	{
		j = i + 1;
		if (is_in2prect(v, vl+i, vl+j))
		{
			if (is_sameline(v, vl+i, vl+j))
			{
				i2ret = TRUE;
				break;
			}
		}
	}

	return i2ret;
}

int pt_in_poly (   const vertex_t* vl, int np,  /* polygon vl with np vertices  */
				const vertex_t* v)
{
	int i, j, k1, k2, c;
	rect_t		rc; 
	vertex_t	w;
	if (np < 3)
		return 0; 

	vertices_get_extent(vl, np, &rc);
	if ((v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) != 0)
	{
		return FALSE;
	}

	/* Set a horizontal beam l(*v, w) from v to the ultra right */   
	w.x = rc.max_x + (pointVertex)DBL_EPSILON;
	w.y = v->y;

	c = 0;        /* Intersection points counter */
	for(i=0; i<np; i++)
	{
		j = (i+1) % np;

		if(is_intersect(vl+i, vl+j, v, &w))
		{
			c++;
		}
		else if(vl[i].y==w.y)
		{
			k1 = (np+i-1)%np;
			while(k1!=i && vl[k1].y==w.y)
				k1 = (np+k1-1)%np;

			k2 = (i+1)%np;
			while(k2!=i && vl[k2].y==w.y)
				k2 = (k2+1)%np;

			if(k1 != k2 && is_same(v, &w, vl+k1, vl+k2)==0)
				c++;

			if(k2 <= i)
				break;

			i = k2;
		}
	}
	return   c%2;
}
#if 0
int pt_in_trianglestrip (   const vertex_t* vl, int np,  /* polygon vl with np vertices  */
				const vertex_t* v)
{
	int i, j, k1, k2, c;
	int			nptmp = 0;
	rect_t		rc; 
	vertex_t	w;
	vertex_t	vtmp[1024];
	if (np < 3)
		return 0; 

	TS2Pol(vtmp, &nptmp, vl, np);
	vertices_get_extent(vtmp, nptmp, &rc);
	if ((v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) != 0)
	{
		return FALSE;
	}

	/* Set a horizontal beam l(*v, w) from v to the ultra right */   
	w.x = rc.max_x + (pointVertex)DBL_EPSILON;
	w.y = v->y;

	c = 0;        /* Intersection points counter */
	for(i=0; i<nptmp; i++)
	{
		j = (i+1) % nptmp;

		if(is_intersect(vtmp+i, vtmp+j, v, &w))
		{
			c++;
		}
		else if(vtmp[i].y==w.y)
		{
			k1 = (nptmp+i-1)%nptmp;
			while(k1!=i && vtmp[k1].y==w.y)
				k1 = (nptmp+k1-1)%nptmp;

			k2 = (i+1)%nptmp;
			while(k2!=i && vtmp[k2].y==w.y)
				k2 = (k2+1)%nptmp;

			if(k1 != k2 && is_same(v, &w, vtmp+k1, vtmp+k2)==0)
				c++;

			if(k2 <= i)
				break;

			i = k2;
		}
	}
	return   c%2;
}
#else
#define vlTmpNum 3
int pt_in_trianglestrip (   const vertex_t* vl, int np,  /* polygon vl with np vertices  */
				const vertex_t* v)
{
	int i = 0;
	int j = 0;
	short i2ret = FALSE;
	rect_t		rc;
	vertex_t	vlTmp[vlTmpNum];
	if (np < 3)
		return 0; 

	vertices_get_extent(vl, np, &rc);
	if ((v->x < rc.min_x || v->x > rc.max_x || v->y < rc.min_y || v->y > rc.max_y) != 0)
	{
		return FALSE;
	}

	for(i=0; i<np-vlTmpNum + 1; i++)
	{
		for (j=0; j<vlTmpNum; j++)
		{
			vlTmp[j].x = (vl+i+j)->x;
			vlTmp[j].y = (vl+i+j)->y;
			vlTmp[j].z = (vl+i+j)->z;
		}
		if (pt_in_poly(vlTmp, vlTmpNum, v))
		{
			i2ret = TRUE;
			break;
		}
	}
	return   i2ret;
}
#endif
